This invention relates to systems and methods for controlling traffic to particular destinations (“data flows”) on a network. The invention accomplishes this using a time-based queuing system comprising a series of queues, each of which buffers packets for a defined length of time.
Traffic shaping involves limiting the rate at which data is transmitted to particular locations on a network (e.g., to network interfaces or network destinations). This may be employed to prevent congestion on a particular network segment or to limit a network entity to the amount of bandwidth that it has paid for. A network employs a “policing” algorithm to determine when traffic to or from a particular network user should be limited.
If a policing algorithm determines that the network interface is at a maximum usage rate, it may limit the flow of network traffic accordingly. Typically, traffic flow is limited by simply discarding or dropping packets to or from a network interface. This means that the discarded packets must be retransmitted at a later time when the network flow is not at the maximum level allowed by the policing algorithm. Administration of the retransmissions is handled by TCP or other relatively high level network protocol. Putting this burden on TCP often places too much responsibility on the protocol (which plays many other roles in administering network traffic) and thereby greatly reduces the network performance. This may be manifest by short periods of very bursty traffic followed by extended quiet periods.
One potential solution to this difficulty employs separate queues for each individual interface or destination that requires flow control. Unfortunately, this solution does not scale well for systems having many destinations. Each new network destination requires a new and separate queue. And each new separate queue requires its own additional memory and its own additional CPU resources (overhead to identify the appropriate queue, etc.). If a system needs to service 5000 destinations, then it also needs to provide and service 5000 distinct queues.
What is needed, therefore, is an improved technique for traffic shaping on a per-destination basis. The technique should not unnecessarily discard packets when a maximum flow rate is exceeded and should not rely on a single queue for each destination under consideration.